minHeap = {}

local function _compare(a,b)
	return a < b
end
local function swap( a,b )
	return b,a
end
function minHeap:newHeap(cmp,arr)
	local o = {}
	setmetatable(o, {__index = self})
	o.cmp = cmp or _compare
	o.arr = {}
	if arr then
		for i,v in ipairs(arr) do
			o:push(v)
		end
	end
	return o
end

function minHeap:pop( )
	self.arr[1] = self.arr[#self.arr]
	table.remove(self.arr)
	self:pushDown()
end

function minHeap:push( num )
	table.insert(self.arr,num)
	self:pushUp()
end

function minHeap:pushUp()
	local st = #self.arr
	local ed = 1
	while st >= ed do
		local parent = math.floor(st / 2)
		if parent < ed then
			break
		end
		if self.cmp(self.arr[st],self.arr[parent]) then
			self.arr[parent],self.arr[st] = swap(self.arr[parent],self.arr[st])
			st = parent
		else
			break
		end
	end
end

function minHeap:pushDown()
	local st = 1
	local ed = #self.arr
	while st <= ed do
		local lc = st * 2
		local rc = lc + 1
		local cidx = lc
		if lc > ed then
			break
		end
		if rc <= ed then
			if not self.cmp(self.arr[lc] , self.arr[rc]) then
				cidx = rc
			end
		end
		if self.cmp(self.arr[cidx],self.arr[st]) then
			self.arr[cidx],self.arr[st] = swap(self.arr[cidx],self.arr[st])
			st = cidx
		else
			break
		end
	end
end

local function _tostring( tab )
	local str = "["
	if type(tab) == 'table' then
		for k,v in pairs(tab) do
			if type(v) == 'table' then
				str = str .. _tostring(v)
			else
				str = str ..v.." , "
			end
		end
	else
		str = str..tab
	end
	str = str.."],"
	return str
end

--[[只支持普通数组的打印，方便测试]]
function minHeap:print( key )
	local str = ""
	for i,v in ipairs(self.arr) do
		str = str .. _tostring(v) .. " "
	end
	print(str)
end

function minHeap:top()
	return self.arr[1]
end